package com.jia.interviewPro;

/**
 * 面试题 16.05. 阶乘尾数
 */
public class Pro1605 {
    /*
    n! = 1 * 2 * 3 * 4 * (1 * 5) * ... * (2 * 5) * ... * (3 * 5) ...
    我们发现，
    每隔 5 个数就会出现 一个 5，因此我们只需要通过 n / 5 来计算存在存在多少个 5 个数，那么就对应的存在多少个 5
    但是，我们也会发现
    每隔 25 个数会出现 一个 25， 而 25 存在 两个 5，我们上面只计算了 25 的一个 5，因此我们需要 n / 25 来计算存在多少个 25，加上它遗漏的 5
    同时，我们还会发现
    每隔 125 个数会出现一个 125，而 125 存在 三个 5，我们上面只计算了 125 的两个 5，因此我们需要 n / 125 来计算存在多少个 125，加上它遗漏的 5
            ...

    因此我们 count = n / 5 + n / 25 + n / 125 + ...
    最终分母可能过大溢出，上面的式子可以进行转换

            count = n / 5 + n / 5 / 5 + n / 5 / 5 / 5 + ...
    因此，我们这样进行循环
    n /= 5;
    count += n;
    这样，第一次加上的就是 每隔 5 个数的 5 的个数，第二次加上的就是 每隔 25 个数的 5 的个数 ...
            */
    public int trailingZeroes(int n) {
        int count = 0;
        while(n >= 5) {
            n /= 5;
            count += n;
        }
        return count;
    }
    /**
     *执行结果：
     超出时间限制
     显示详情
     最后执行的输入：
     1808548329
     **/
    public int trailingZeroes2(int n) {
        int count5 = 0;
        for(int i = 2; i <= n; i++) {
            count5 += h5(i);
        }
        return count5;
    }
    private int h5(int num) {
        int count = 0;
        while(num != 0){
            if(num % 5 == 0) {
                num /= 5;
                ++count;
            }else { break;}
        }
        return count;
    }
}
